public class demo {
    public static void main(String[] args) {
        System.out.println("单链表的排序,链表内的值都取出来，放入数组内排序，再创建一个新链表，把他们放入到新链表内");
        System.out.println("import java.util.*;\n" +
                "\n" +
                "/*\n" +
                " * public class ListNode {\n" +
                " *   int val;\n" +
                " *   ListNode next = null;\n" +
                " *   public ListNode(int val) {\n" +
                " *     this.val = val;\n" +
                " *   }\n" +
                " * }\n" +
                " */\n" +
                "\n" +
                "public class Solution {\n" +
                "    /**\n" +
                "     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可\n" +
                "     *\n" +
                "     * \n" +
                "     * @param head ListNode类 the head node\n" +
                "     * @return ListNode类\n" +
                "     */\n" +
                "    public ListNode sortInList (ListNode head) {\n" +
                "        // write code here\n" +
                "        if(head == null) return head;\n" +
                "\n" +
                "        ListNode cur = head;\n" +
                "        int ret = 0;\n" +
                "        while(cur != null){\n" +
                "            cur = cur.next;\n" +
                "            ret += 1;\n" +
                "        }\n" +
                "\n" +
                "        int[] arr = new int[ret];\n" +
                "        cur = head;\n" +
                "        ret = 0;\n" +
                "        while(cur != null){\n" +
                "            arr[ret] = cur.val;\n" +
                "            cur = cur.next;\n" +
                "            ret++;\n" +
                "        }\n" +
                "\n" +
                "        Arrays.sort(arr);\n" +
                "\n" +
                "        ListNode pre = new ListNode(0);\n" +
                "        ListNode tmp = pre;\n" +
                "        for(int i = 0; i < arr.length; i++){\n" +
                "            tmp.next = new ListNode(arr[i]);\n" +
                "            tmp = tmp.next;\n" +
                "        }\n" +
                "\n" +
                "        return pre.next;\n" +
                "    }\n" +
                "}");
    }
}
